HW#2 --- last modified January 29 2019 04:28:27.

Solution set.

Due date: Oct 11

Files to be submitted:
  Hw2.zip

Purpose: To reason about the hill-climbing, simulated annealing, and genetic algorithms. To code the minimax algorithm with alpha-beta pruning in a specific context.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO6 -- Students should be able to explain the advantages and disadvantages of hill climbing.

LO8 -- Students should be able to explain the advantages and disadvantages of alpha-beta pruning.

Specification:

This homework consists of a written component and a coding component. Files for both components should be submitted in your Hw2.zip file along with a readme.txt with any additional instructions, a list of your team mates and their IDs. For the written part, please do the following problems and submit them in a file Hw2.pdf within the Hw2.zip file. Each of these problems is related to the Traveling Salesman Problem connected to the weighted, undirected graph below. Recall in the traveling salesman problem we are trying to find a path which visits each node in the graph without repeats, such that the sum of the edges along this path is as small as possible.

1. Suppose we start with the path ABCDE, what is its cost? Call two paths adjacent if they can be obtained from each other by a single swap. The result of the swap is required to be a path in the graph. For example, CBADE is adjacent to ABCDE, but DBCAE is not because the result is not a path in the graph above. Write down all the paths and their costs that are adjacent to ABCDE. Which is of least cost? Pick this smallest path as a start point and find its adjacent path of smallest cost. This would be the result of doing the hill-climbing algorithm for two steps.
2. Give a path in the above graph which is not the path of minimal cost (ADEBC) but which is of local minimum cost with respect to its immediately adjacent paths.
3. Consider the following alternative notation for paths in the above graph: a sequence of five numbers, the first in the range 1 to 5, the second with range 1 to 4, etc. For example, 43221. The number 4 represents the fourth letter among the currently remaining letters A,B,C,D,E, so is the letter D. The number 3 represents third letter among the currently remaining letters A,B,C,E, so is C. Computing in this fashion, we get the path DCBEA (the last letter is always 1 so we could shorten the sequence to 4322). Generate two paths by rolling dice to pick numbers. If the number is too high for the current position re-roll. Use these two path as the starting paths for a 2-local beam search of traveling salesman paths in this graph. Write the initial paths, generate and write down their adjacent paths with computed costs, pick the two of least costs and do this again one more time for these two paths, so you show you understand the idea of 2-local beam search.
4. Starting with the same two paths you rolled above in number notation, randomly pick a number between 1-3. Breed these two path by using the number you just rolled as a crossover point. Is the result a path? If not, are their any values between 1-3 which if used as a crossover point would result in paths?

For the coding part of this assignment I would like you to write a Python program, push_four.py to play the two player game Push Four, which I invented for this homework. Push Four is play on a 7x7 board. Each board square has one of three symbols in it X, O, or E. We call the first player, Player X, plays x pieces, the second player, Player O, plays O pieces. The goal of the game is to get four in a row of your piece, either horizontally, vertically, or diagonally. Initially, the board should appear all empty (with E's in each square) like:

         N
    A B C D c b a
   +-+-+-+-+-+-+-+
  A|E|E|E|E|E|E|E|A
   +-+-+-+-+-+-+-+
  B|E|E|E|E|E|E|E|B
   +-+-+-+-+-+-+-+
  C|E|E|E|E|E|E|E|C
W  +-+-+-+-+-+-+-+  E
  D|E|E|E|E|E|E|E|D
   +-+-+-+-+-+-+-+
  c|E|E|E|E|E|E|E|c
   +-+-+-+-+-+-+-+
  b|E|E|E|E|E|E|E|b
   +-+-+-+-+-+-+-+
  a|E|E|E|E|E|E|E|a
   +-+-+-+-+-+-+-+
    A B C D c b a
         S

A move consists of a direction (N,E,W,S) together with a letter from A,B,C,D,c,b,a. It has the effect of inserting a piece on that side of the board in the given row or column and pushing the remaining piece over by 1, with the last piece in the row or column being removed. For example, if Player X moved WB on the empty board above. The new board would look like:

         N
    A B C D c b a
   +-+-+-+-+-+-+-+
  A|E|E|E|E|E|E|E|A
   +-+-+-+-+-+-+-+
  B|X|E|E|E|E|E|E|B
   +-+-+-+-+-+-+-+
  C|E|E|E|E|E|E|E|C
W  +-+-+-+-+-+-+-+  E
  D|E|E|E|E|E|E|E|D
   +-+-+-+-+-+-+-+
  c|E|E|E|E|E|E|E|c
   +-+-+-+-+-+-+-+
  b|E|E|E|E|E|E|E|b
   +-+-+-+-+-+-+-+
  a|E|E|E|E|E|E|E|a
   +-+-+-+-+-+-+-+
    A B C D c b a
         S

If Player O moves NA, on this board, the result would look like:

         N
    A B C D c b a
   +-+-+-+-+-+-+-+
  A|O|E|E|E|E|E|E|A
   +-+-+-+-+-+-+-+
  B|E|E|E|E|E|E|E|B
   +-+-+-+-+-+-+-+
  C|X|E|E|E|E|E|E|C
W  +-+-+-+-+-+-+-+  E
  D|E|E|E|E|E|E|E|D
   +-+-+-+-+-+-+-+
  c|E|E|E|E|E|E|E|c
   +-+-+-+-+-+-+-+
  b|E|E|E|E|E|E|E|b
   +-+-+-+-+-+-+-+
  a|E|E|E|E|E|E|E|a
   +-+-+-+-+-+-+-+
    A B C D c b a
         S

Notice how all the squares in the first column moved down by 1, with the last one being deleted. That is why the X which had been in the second row is now in the third row.

The game has one other rule called the SAME LETTER RULE: If the last move of the other player in involved a given non-direction letter then the next move cannot involve either the upper or lower case version of that letter. So on the above board, Player X cannot make any move involving the letter A or a. In particular, Player X cannot play EA to push Player O's piece off the board.

Your program will be run from the command line by the grader with a line like:

python push_four.py

Would you like to go first (y/n)?

If the answer is y, Player X is assumed to be human and Player O is played by the computer. Otherwise, if the answer is n, Player O is assumed to be human and Player X is played by the computer. Your program should then start the game. Before each human player move your program should:

1. State the last human move.
2. State the last computer move.
3. Draw the game board.
4. State if the game has ended, and if so, who won.
5. Prompt the human player for a move, if the game is not over.

Below is a short example game:

Would you like to go first (y/n)?
y
You have not moved yet
Player O has not moved yet
         N
    A B C D c b a
   +-+-+-+-+-+-+-+
  A|E|E|E|E|E|E|E|A
   +-+-+-+-+-+-+-+
  B|E|E|E|E|E|E|E|B
   +-+-+-+-+-+-+-+
  C|E|E|E|E|E|E|E|C
W  +-+-+-+-+-+-+-+  E
  D|E|E|E|E|E|E|E|D
   +-+-+-+-+-+-+-+
  c|E|E|E|E|E|E|E|c
   +-+-+-+-+-+-+-+
  b|E|E|E|E|E|E|E|b
   +-+-+-+-+-+-+-+
  a|E|E|E|E|E|E|E|a
   +-+-+-+-+-+-+-+
    A B C D c b a
         S
Please enter a move (direction letter from N,E,W,S followed by a row or column letter):NC
You played NC
Player O moves WA
         N
    A B C D c b a
   +-+-+-+-+-+-+-+
  A|O|E|E|X|E|E|E|A
   +-+-+-+-+-+-+-+
  B|E|E|E|E|E|E|E|B
   +-+-+-+-+-+-+-+
  C|E|E|E|E|E|E|E|C
W  +-+-+-+-+-+-+-+  E
  D|E|E|E|E|E|E|E|D
   +-+-+-+-+-+-+-+
  c|E|E|E|E|E|E|E|c
   +-+-+-+-+-+-+-+
  b|E|E|E|E|E|E|E|b
   +-+-+-+-+-+-+-+
  a|E|E|E|E|E|E|E|a
   +-+-+-+-+-+-+-+
    A B C D c b a
         S
Please enter a move (direction letter from N,E,W,S followed by a row or column letter):ND
You played ND
Player O moves WB
         N
    A B C D c b a
   +-+-+-+-+-+-+-+
  A|O|E|E|X|E|E|E|A
   +-+-+-+-+-+-+-+
  B|O|E|E|E|X|E|E|B
   +-+-+-+-+-+-+-+
  C|E|E|E|E|E|E|E|C
W  +-+-+-+-+-+-+-+  E
  D|E|E|E|E|E|E|E|D
   +-+-+-+-+-+-+-+
  c|E|E|E|E|E|E|E|c
   +-+-+-+-+-+-+-+
  b|E|E|E|E|E|E|E|b
   +-+-+-+-+-+-+-+
  a|E|E|E|E|E|E|E|a
   +-+-+-+-+-+-+-+
    A B C D c b a
         S
Please enter a move (direction letter from N,E,W,S followed by a row or column letter):ED
You played ED
Player O moves WC
         N
    A B C D c b a
   +-+-+-+-+-+-+-+
  A|O|E|E|X|E|E|E|A
   +-+-+-+-+-+-+-+
  B|O|E|E|E|X|E|E|B
   +-+-+-+-+-+-+-+
  C|O|E|E|E|E|E|E|C
W  +-+-+-+-+-+-+-+  E
  D|E|E|E|E|E|E|X|D
   +-+-+-+-+-+-+-+
  c|E|E|E|E|E|E|E|c
   +-+-+-+-+-+-+-+
  b|E|E|E|E|E|E|E|b
   +-+-+-+-+-+-+-+
  a|E|E|E|E|E|E|E|a
   +-+-+-+-+-+-+-+
    A B C D c b a
         S
Please enter a move (direction letter from N,E,W,S followed by a row or column letter):ED
You played ED
Player O moves NA
         N
    A B C D c b a
   +-+-+-+-+-+-+-+
  A|O|E|E|X|E|E|E|A
   +-+-+-+-+-+-+-+
  B|O|E|E|E|X|E|E|B
   +-+-+-+-+-+-+-+
  C|O|E|E|E|E|E|E|C
W  +-+-+-+-+-+-+-+  E
  D|O|E|E|E|E|X|X|D
   +-+-+-+-+-+-+-+
  c|E|E|E|E|E|E|E|c
   +-+-+-+-+-+-+-+
  b|E|E|E|E|E|E|E|b
   +-+-+-+-+-+-+-+
  a|E|E|E|E|E|E|E|a
   +-+-+-+-+-+-+-+
    A B C D c b a
         S
Player O Wins! You Lose!

When the game completes your program should return to the command prompt. To make its move, your computer player should use the minimax algorithm with alpha beta pruning. At the top of your push_four.py program you should clearly say where to find the code for minimax and alpha-beta pruning. This completes the description of the homework.

Point Breakdown